Merge Sort採用Divide and Conquer的方式，其實他的概念本身就是遞迴（recursion）。

Divide and Conquer的作法一般分成三個步驟：

1. Divide ：把問題先拆解成子問題
2. Conquer：利用遞迴逐一處理子問題，當子問題夠小時則可以直接解（利用初始條件）
3. Combine：將子問題的結果合併

而今天會用兩種方式來實作合併排序

	  index    0,1,2,3,4,5
Input: nums = [5,1,1,2,0,0]

我們一樣用這個範例來舉例
首先我們要把這個陣列不斷的拆分成兩半
像下面這樣

我們先看左邊
[5, 1, 1, 2, 0, 0]
[5, 1, 1][2, 0, 0]
[5][1, 1]
[5][1][1]

當我們遇到拆完兩個subArray的長度恰為１的時候，我們就比較他們大小並重新建立新的已經排序好的subArray直到長度和原本的input array相同

左半邊有長度1的子陣列
我們開始對他們排序
[5][1][1] -> 長度１很好比大小
接著因為我們知道兩子陣列都已經排序過了，可以利用兩個指標的方式來對他們合併
[1,5][1] -> 因為 1 <=1 ,把L指的數家到新的subArray[1]
 ^    ^
 |    |
 L    R
---------
[1,5][1] -> 因為 5 > 1 ,把R指的數家到新的subArray[1,1]
   ^  ^
   |  |
   L  R

----------
最後得到
[1,1,5]

利用上面的方式我們繼續處理右半邊

[5, 1, 1, 2, 0, 0]
[5, 1, 1][2, 0, 0]
[5][1, 1][2] [0,0]
[5][1][1][2][0][0]
-----------------
[1,1,5] [0,0,2]
一樣用指標來做最後合併
[0,0,1,1,2,5]

先來看時間複雜度，過程中可以發現我們第一次複製並產生新的兩個subArray且到最後仍要合併他們都會需要O(N)。
可以觀察到每一層的subArray都會是上一層的一半，而且每一層的時間複雜度為O(N)，所以我們應該要思考，應該是幾層(level)？
來稍微算一下，Ｎ(array的長度)＝ ２^level ⇒ level = logN
所以說，整體的時間約為O(NlogN)，而這種方式不是in place sort，空間複雜度為O(NlogN)

function mergeSort(array) {
  if (array.length <= 1) return array;
  const midInx = Math.floor(array.length / 2);
  const leftHalf = array.slice(0, midInx);
  const rightHalf = array.slice(midInx);
  return merge(mergeSort(leftHalf), mergeSort(rightHalf));
}

function merge(leftHalf, rightHalf) {
  const sortedArr = new Array(leftHalf.length + rightHalf.length);
  // k 指向 sortedArr
  let k = 0;
  // i 指向 左半
  let i = 0;
  // j 指向 右半
  let j = 0;
  while (i < leftHalf.length && j < rightHalf.length) {
    if (leftHalf[i] <= rightHalf[j]) {
      sortedArr[k++] = leftHalf[i++];
    } else {
      sortedArr[k++] = rightHalf[j++];
    }
  }
  // 做完後如果左半或右半還有剩元素 要繼續放入sortedArr
  while (i < leftHalf.length) {
    sortedArr[k++] = leftHalf[i++];
  }
  while (j < rightHalf.length) {
    sortedArr[k++] = rightHalf[j++];
  }
  return sortedArr;
}

接下來我們要來思考怎麼改善空間複雜度，利用in place的方式，並且達到時間複雜度也是Ｏ(NlogN)。
我們先限制自己只能用一個input array的拷貝，這裡我們拿拷貝來當主要操作的陣列。建立一個helper function來把他們當作參數來操作。

流程如下

inputArr = [5, 1, 1, 2, 0, 0] -
                               ｜呼叫helper function
copyArr =  [5, 1, 1, 2, 0, 0] -

  inputArr [5, 1, 1]-
                     ｜呼叫helper function
  copyArr  [5, 1, 1]-

  inputArr [5,1][1]-
                     ｜呼叫helper function
   copyArr [5,1][1]-

  inputArr [5][1]-
                  ｜呼叫helper（但會直接return），而後再一個個執行合併(merge)的方法
  copyArr  [5][1]-

直到最後陣列長度為1的時候，我們要把陣列做合併的動作(mergeArr)
我們要把他合併成長度為二且排列後的陣列
假設目前的左半邊合併是

inputArr = [5, 1, 1, 2, 0, 0] 
copyArr =  [5, 1, 1, 2, 0, 0] 

inputArr [5, 1, 1]
copyArr  [5, 1, 1]
inputArr [5,1][1]
copyArr  [5,1][1]

----------------
inputArr [5,1]                  
copyArr  [5,1]
          ^ ^
          L R
我們用LR指標比大小 然後因為1(R)< 5(L)
我們就直接把inputArr[0]改成1,inputArr[1]改成5
也就是說我們會直接改inputArr [1,5,1,2,0,0]  
以小的部分來看，原本的
inputArr [5,1,1]
copyArr  [5,1,1]
會變成
inputArr [1,1,5]
copyArr  [5,1,1]
全部
inputArr [1,1,5,2,0,0] 
這就是原地置換(In-Place)的方式

那為什麼我們需要一個拷貝來當作輔助？

inputArr [5,1]                  
copyArr  [5,1]
          ^ ^
          L R
以這個例子來說我們在更改的時候因為把1(R)要變更inputArr[0]，也就是5要變1
如果我們沒有拷貝
inputArr現在會長[1,1]  
這樣5就完全消失了

function mergeSort(array) {
  if (array.length <= 1) return array;
  const copyArr = array.slice();
  helper(array, 0, array.length - 1, copyArr);
  return array;
}

function helper(inputArray, startIdx, endIdx, copyArr) {
  if (startIdx === endIdx) return;
  const midIdx = Math.floor((startIdx + endIdx) / 2);
  helper(copyArr, startIdx, midIdx, inputArray);
  helper(copyArr, midIdx + 1, endIdx, inputArray);
  merge(inputArray, startIdx, midIdx, endIdx, copyArr);
}
function merge(inputArray, startIdx, midIdx, endIdx, copyArr) {
  let k = startIdx;
  let i = startIdx;
  let j = midIdx + 1;
  while (i <= midIdx && j <= endIdx) {
    if (copyArr[i] <= copyArr[j]) {
      inputArray[k++] = copyArr[i++];
    } else {
      inputArray[k++] = copyArr[j++];
    }
  }

  while (i <= midIdx) {
    inputArray[k++] = copyArr[i++];
  }
  while (j <= endIdx) {
    inputArray[k++] = copyArr[j++];
  }
}

明天是排序的最後一次拉！

明日實作：堆積排序法(Heap Sort)